package jm.data.structure.union_find;

/**
 * @Description QuickFind 实现并查集
 * @date 2022/5/9 17:06
 */
public class QuickFind extends AbstractUnionFind{

    public QuickFind(int capacity) {
        super(capacity);
    }

    @Override
    public int find(int v) {
        rangeCheck(v);
        // 因为这里直接指向的就是根节点，所以直接返回即可
        return parents[v];
    }

    @Override
    public void union(int v1, int v2) {
        // 获取两个值所在的集合（根节点值）
        int p1 = find(v1);
        int p2 = find(v2);
        // 如果根节点相同 就表示位于同一个集合中不需要合并
        if (p1 == p2) return;

        // 遍历数组中所有的元素，如果根节点与 v1 相同的都改为 v2 的根节点
        for (int i = 0; i < parents.length; i++) {
            if (parents[i] == p1){
                parents[i] = p2;
            }
        }
    }
}
